In applied mathematics, a bit-reversal permutation is a permutation of a sequence with n = 2m (a power of two) elements, defined by reversing the binary digits of the index (0 to n − 1) of each element. The generalization to n = bm for an arbitrary integer b > 1 is a base-b digit-reversal permutation, in which the base-b (radix-b) digits of the index of each element are reversed to obtain the permuted index. A further generalization to arbitrary composite sizes is a mixed-radix digit reversal (in which the elements of the sequence are indexed by a number expressed in a mixed radix, whose digits are reversed by the permutation).
Bit reversal is most important for radix-2 Cooley–Tukey FFT algorithms, where the recursive stages of the algorithm, operating in-place, imply a bit reversal of the inputs or outputs. Similarly, mixed-radix digit reversals arise in mixed-radix Cooley–Tukey FFTs. Mainly because of the importance of fast Fourier transform (FFT) algorithms, numerous efficient O(n) in-place algorithms for bit-reversal and digit-reversal permutations have been devised.[1][2][3][4][5][6]